// https://leetcode.cn/problems/valid-palindrome-ii/
// Created by ade on 2022/8/12.
// 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
#include <iostream>
#include <string>


using namespace std;

class Solution {
public:
    bool flag = false;

    bool validPalindrome(string s) {
        isPalindrome(s, 0, s.size() - 1, 0);
        return flag;
    }

    void isPalindrome(const string &s, int left, int right, int count) {
        if (count > 1) return;
        if (left >= right) {
            flag = true;
            return;
        }
        if (s[left] == s[right]) {
            isPalindrome(s, left + 1, right - 1, count);
        } else {
            if (s[left + 1] == s[right]) {
                isPalindrome(s, left + 1, right, count + 1);
            }
            if (s[left] == s[right - 1]) {
                isPalindrome(s, left, right - 1, count + 1);
            }
        }
    }
};


int main() {
    Solution so;
    string a = "cuppucu";
    auto res = so.validPalindrome(a);
    cout << res << endl;
    return 0;
}